/*
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 * LAGDHillClimber.java
 * Copyright (C) 2005-2012 Manuel Neubach
 * 
 */

package weka.classifiers.bayes.net.search.local;

import java.util.Collections;
import java.util.Enumeration;
import java.util.Vector;

import weka.classifiers.bayes.BayesNet;
import weka.core.Instances;
import weka.core.Option;
import weka.core.Utils;

/**
 * <!-- globalinfo-start --> This Bayes Network learning algorithm uses a Look
 * Ahead Hill Climbing algorithm called LAGD Hill Climbing. Unlike Greedy Hill
 * Climbing it doesn't calculate a best greedy operation (adding, deleting or
 * reversing an arc) but a sequence of nrOfLookAheadSteps operations, which
 * leads to a network structure whose score is most likely higher in comparison
 * to the network obtained by performing a sequence of nrOfLookAheadSteps greedy
 * operations. The search is not restricted by an order on the variables (unlike
 * K2). The difference with B and B2 is that this hill climber also considers
 * arrows part of the naive Bayes structure for deletion.
 * <p/>
 * <!-- globalinfo-end -->
 * 
 * <!-- options-start --> Valid options are:
 * <p/>
 * 
 * <pre>
 * -L &lt;nr of look ahead steps&gt;
 *  Look Ahead Depth
 * </pre>
 * 
 * <pre>
 * -G &lt;nr of good operations&gt;
 *  Nr of Good Operations
 * </pre>
 * 
 * <pre>
 * -P &lt;nr of parents&gt;
 *  Maximum number of parents
 * </pre>
 * 
 * <pre>
 * -R
 *  Use arc reversal operation.
 *  (default false)
 * </pre>
 * 
 * <pre>
 * -N
 *  Initial structure is empty (instead of Naive Bayes)
 * </pre>
 * 
 * <pre>
 * -mbc
 *  Applies a Markov Blanket correction to the network structure, 
 *  after a network structure is learned. This ensures that all 
 *  nodes in the network are part of the Markov blanket of the 
 *  classifier node.
 * </pre>
 * 
 * <pre>
 * -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
 *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)
 * </pre>
 * 
 * <!-- options-end -->
 * 
 * @author Manuel Neubach
 * @version $Revision$
 */
public class LAGDHillClimber extends HillClimber {

    /** for serialization */
    static final long serialVersionUID = 7217437499439184344L;

    /** Number of Look Ahead Steps **/
    int m_nNrOfLookAheadSteps = 2;

    /** Number of Good Operations per Step **/
    int m_nNrOfGoodOperations = 5;

    /**
     * search determines the network structure/graph of the network
     * 
     * @param bayesNet  the network
     * @param instances the data to use
     * @throws Exception if something goes wrong
     */
    @Override
    protected void search(BayesNet bayesNet, Instances instances) throws Exception {
        int k = m_nNrOfLookAheadSteps; // Number of Look Ahead Steps
        int l = m_nNrOfGoodOperations; // Number of Good Operations per step
        lookAheadInGoodDirectionsSearch(bayesNet, instances, k, l);
    } // search

    /**
     * lookAheadInGoodDirectionsSearch determines the network structure/graph of the
     * network with best score according to LAGD Hill Climbing
     * 
     * @param bayesNet           the network
     * @param instances          the data to use
     * @param nrOfLookAheadSteps
     * @param nrOfGoodOperations
     * @throws Exception if something goes wrong
     */
    protected void lookAheadInGoodDirectionsSearch(BayesNet bayesNet, Instances instances, int nrOfLookAheadSteps, int nrOfGoodOperations) throws Exception {
        System.out.println("Initializing Cache");
        initCache(bayesNet, instances);

        while (nrOfLookAheadSteps > 1) {
            System.out.println("Look Ahead Depth: " + nrOfLookAheadSteps);
            boolean legalSequence = true;
            double sequenceDeltaScore = 0;
            Operation[] bestOperation = new Operation[nrOfLookAheadSteps];

            bestOperation = getOptimalOperations(bayesNet, instances, nrOfLookAheadSteps, nrOfGoodOperations);
            for (int i = 0; i < nrOfLookAheadSteps; i++) {
                if (bestOperation[i] == null) {
                    legalSequence = false;
                } else {
                    sequenceDeltaScore += bestOperation[i].m_fDeltaScore;
                }
            }
            while (legalSequence && sequenceDeltaScore > 0) {
                System.out.println("Next Iteration..........................");
                for (int i = 0; i < nrOfLookAheadSteps; i++) {
                    performOperation(bayesNet, instances, bestOperation[i]);
                }
                bestOperation = getOptimalOperations(bayesNet, instances, nrOfLookAheadSteps, nrOfGoodOperations);
                sequenceDeltaScore = 0;
                for (int i = 0; i < nrOfLookAheadSteps; i++) {
                    if (bestOperation[i] != null) {
                        System.out.println(bestOperation[i].m_nOperation + " " + bestOperation[i].m_nHead + " " + bestOperation[i].m_nTail);
                        sequenceDeltaScore += bestOperation[i].m_fDeltaScore;
                    } else {
                        legalSequence = false;

                    }
                    System.out.println("DeltaScore: " + sequenceDeltaScore);
                }
            }
            --nrOfLookAheadSteps;
        }

        /** last steps with greedy HC **/
        Operation oOperation = getOptimalOperation(bayesNet, instances);
        while ((oOperation != null) && (oOperation.m_fDeltaScore > 0)) {
            performOperation(bayesNet, instances, oOperation);
            System.out.println("Performing last greedy steps");
            oOperation = getOptimalOperation(bayesNet, instances);
        }
        // free up memory
        m_Cache = null;
    } // lookAheadInGoodDirectionsSearch

    /**
     * getAntiOperation determines the Operation, which is needed to cancel
     * oOperation
     * 
     * @param oOperation Operation to cancel
     * @return antiOperation to oOperation
     * @throws Exception if something goes wrong
     */
    protected Operation getAntiOperation(Operation oOperation) throws Exception {
        if (oOperation.m_nOperation == Operation.OPERATION_ADD) {
            return (new Operation(oOperation.m_nTail, oOperation.m_nHead, Operation.OPERATION_DEL));
        } else {
            if (oOperation.m_nOperation == Operation.OPERATION_DEL) {
                return (new Operation(oOperation.m_nTail, oOperation.m_nHead, Operation.OPERATION_ADD));
            } else {
                return (new Operation(oOperation.m_nHead, oOperation.m_nTail, Operation.OPERATION_REVERSE));
            }
        }
    } // getAntiOperation

    /**
     * getGoodOperations determines the nrOfGoodOperations best Operations, which
     * are considered for the calculation of an optimal operationsequence
     * 
     * @param bayesNet           Bayes network to apply operation on
     * @param instances          data set to learn from
     * @param nrOfGoodOperations number of good operations to consider
     * @return good operations to consider
     * @throws Exception if something goes wrong
     **/
    protected Operation[] getGoodOperations(BayesNet bayesNet, Instances instances, int nrOfGoodOperations) throws Exception {
        Operation[] goodOperations = new Operation[nrOfGoodOperations];
        for (int i = 0; i < nrOfGoodOperations; i++) {
            goodOperations[i] = getOptimalOperation(bayesNet, instances);
            if (goodOperations[i] != null) {
                m_Cache.put(goodOperations[i], -1E100);
            } else {
                i = nrOfGoodOperations;
            }
        }
        for (int i = 0; i < nrOfGoodOperations; i++) {
            if (goodOperations[i] != null) {
                if (goodOperations[i].m_nOperation != Operation.OPERATION_REVERSE) {
                    m_Cache.put(goodOperations[i], goodOperations[i].m_fDeltaScore);
                } else {
                    m_Cache.put(goodOperations[i], goodOperations[i].m_fDeltaScore - m_Cache.m_fDeltaScoreAdd[goodOperations[i].m_nHead][goodOperations[i].m_nTail]);
                }
            } else {
                i = nrOfGoodOperations;
            }
        }
        return goodOperations;
    } // getGoodOperations

    /**
     * getOptimalOperations determines an optimal operationsequence in respect of
     * the parameters nrOfLookAheadSteps and nrOfGoodOperations
     * 
     * @param bayesNet           Bayes network to apply operation on
     * @param instances          data set to learn from
     * @param nrOfLookAheadSteps number of lood ahead steps to use
     * @param nrOfGoodOperations number of good operations to consider
     * @return optimal sequence of operations in respect to nrOfLookAheadSteps and
     *         nrOfGoodOperations
     * @throws Exception if something goes wrong
     **/
    protected Operation[] getOptimalOperations(BayesNet bayesNet, Instances instances, int nrOfLookAheadSteps, int nrOfGoodOperations) throws Exception {
        if (nrOfLookAheadSteps == 1) { // Abbruch der Rekursion
            Operation[] bestOperation = new Operation[1];
            bestOperation[0] = getOptimalOperation(bayesNet, instances);
            return (bestOperation); // Abbruch der Rekursion
        } else {
            double bestDeltaScore = 0;
            double currentDeltaScore = 0;
            Operation[] bestOperation = new Operation[nrOfLookAheadSteps];
            Operation[] goodOperations = new Operation[nrOfGoodOperations];
            Operation[] tempOperation = new Operation[nrOfLookAheadSteps - 1];
            goodOperations = getGoodOperations(bayesNet, instances, nrOfGoodOperations);
            for (int i = 0; i < nrOfGoodOperations; i++) {
                if (goodOperations[i] != null) {
                    performOperation(bayesNet, instances, goodOperations[i]);
                    tempOperation = getOptimalOperations(bayesNet, instances, nrOfLookAheadSteps - 1, nrOfGoodOperations); // rekursiver Abstieg
                    currentDeltaScore = goodOperations[i].m_fDeltaScore;
                    for (int j = 0; j < nrOfLookAheadSteps - 1; j++) {
                        if (tempOperation[j] != null) {
                            currentDeltaScore += tempOperation[j].m_fDeltaScore;
                        }
                    }
                    performOperation(bayesNet, instances, getAntiOperation(goodOperations[i]));
                    if (currentDeltaScore > bestDeltaScore) {
                        bestDeltaScore = currentDeltaScore;
                        bestOperation[0] = goodOperations[i];
                        for (int j = 1; j < nrOfLookAheadSteps; j++) {
                            bestOperation[j] = tempOperation[j - 1];
                        }
                    }
                } else {
                    i = nrOfGoodOperations;
                }
            }
            return (bestOperation);
        }
    } // getOptimalOperations

    /**
     * Sets the max number of parents
     * 
     * @param nMaxNrOfParents the max number of parents
     */
    @Override
    public void setMaxNrOfParents(int nMaxNrOfParents) {
        m_nMaxNrOfParents = nMaxNrOfParents;
    }

    /**
     * Gets the max number of parents.
     * 
     * @return the max number of parents
     */
    @Override
    public int getMaxNrOfParents() {
        return m_nMaxNrOfParents;
    }

    /**
     * Sets the number of look-ahead steps
     * 
     * @param nNrOfLookAheadSteps the number of look-ahead steps
     */
    public void setNrOfLookAheadSteps(int nNrOfLookAheadSteps) {
        m_nNrOfLookAheadSteps = nNrOfLookAheadSteps;
    }

    /**
     * Gets the number of look-ahead steps
     * 
     * @return the number of look-ahead step
     */
    public int getNrOfLookAheadSteps() {
        return m_nNrOfLookAheadSteps;
    }

    /**
     * Sets the number of "good operations"
     * 
     * @param nNrOfGoodOperations the number of "good operations"
     */
    public void setNrOfGoodOperations(int nNrOfGoodOperations) {
        m_nNrOfGoodOperations = nNrOfGoodOperations;
    }

    /**
     * Gets the number of "good operations"
     * 
     * @return the number of "good operations"
     */
    public int getNrOfGoodOperations() {
        return m_nNrOfGoodOperations;
    }

    /**
     * Returns an enumeration describing the available options.
     * 
     * @return an enumeration of all the available options.
     */
    @Override
    public Enumeration<Option> listOptions() {
        Vector<Option> newVector = new Vector<Option>(2);

        newVector.addElement(new Option("\tLook Ahead Depth", "L", 2, "-L <nr of look ahead steps>"));
        newVector.addElement(new Option("\tNr of Good Operations", "G", 5, "-G <nr of good operations>"));

        newVector.addAll(Collections.list(super.listOptions()));

        return newVector.elements();
    } // listOptions

    /**
     * Parses a given list of options. Valid options are:
     * <p>
     * 
     * <!-- options-start --> Valid options are:
     * <p/>
     * 
     * <pre>
     * -L &lt;nr of look ahead steps&gt;
     *  Look Ahead Depth
     * </pre>
     * 
     * <pre>
     * -G &lt;nr of good operations&gt;
     *  Nr of Good Operations
     * </pre>
     * 
     * <pre>
     * -P &lt;nr of parents&gt;
     *  Maximum number of parents
     * </pre>
     * 
     * <pre>
     * -R
     *  Use arc reversal operation.
     *  (default false)
     * </pre>
     * 
     * <pre>
     * -N
     *  Initial structure is empty (instead of Naive Bayes)
     * </pre>
     * 
     * <pre>
     * -mbc
     *  Applies a Markov Blanket correction to the network structure, 
     *  after a network structure is learned. This ensures that all 
     *  nodes in the network are part of the Markov blanket of the 
     *  classifier node.
     * </pre>
     * 
     * <pre>
     * -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
     *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)
     * </pre>
     * 
     * <!-- options-end -->
     * 
     * @param options the list of options as an array of strings
     * @throws Exception if an option is not supported
     */
    @Override
    public void setOptions(String[] options) throws Exception {
        String sNrOfLookAheadSteps = Utils.getOption('L', options);
        if (sNrOfLookAheadSteps.length() != 0) {
            setNrOfLookAheadSteps(Integer.parseInt(sNrOfLookAheadSteps));
        } else {
            setNrOfLookAheadSteps(2);
        }

        String sNrOfGoodOperations = Utils.getOption('G', options);
        if (sNrOfGoodOperations.length() != 0) {
            setNrOfGoodOperations(Integer.parseInt(sNrOfGoodOperations));
        } else {
            setNrOfGoodOperations(5);
        }

        super.setOptions(options);
    } // setOptions

    /**
     * Gets the current settings of the search algorithm.
     * 
     * @return an array of strings suitable for passing to setOptions
     */
    @Override
    public String[] getOptions() {

        Vector<String> options = new Vector<String>();

        options.add("-L");
        options.add("" + m_nNrOfLookAheadSteps);

        options.add("-G");
        options.add("" + m_nNrOfGoodOperations);

        Collections.addAll(options, super.getOptions());

        return options.toArray(new String[0]);
    } // getOptions

    /**
     * This will return a string describing the search algorithm.
     * 
     * @return The string.
     */
    @Override
    public String globalInfo() {
        return "This Bayes Network learning algorithm uses a Look Ahead Hill Climbing algorithm called LAGD Hill Climbing." + " Unlike Greedy Hill Climbing it doesn't calculate a best greedy operation (adding, deleting or reversing an arc) " + "but a sequence of nrOfLookAheadSteps operations, which leads to a network structure whose score is most likely " + "higher in comparison to the network obtained by performing a sequence of nrOfLookAheadSteps greedy operations. " + "The search is not restricted by an order " + "on the variables (unlike K2). The difference with B and B2 is that this hill " + "climber also considers arrows part of the naive Bayes structure for deletion.";
    } // globalInfo

    /**
     * @return a string to describe the Number of Look Ahead Steps option.
     */
    public String nrOfLookAheadStepsTipText() {
        return "Sets the Number of Look Ahead Steps. 'nrOfLookAheadSteps = 2' means that all network structures in a " + "distance of 2 (from the current network structure) are taken into account for the decision which arcs to add, " + "remove or reverse. 'nrOfLookAheadSteps = 1' results in Greedy Hill Climbing.";
    } // nrOfLookAheadStepsTipText

    /**
     * @return a string to describe the Number of Good Operations option.
     */
    public String nrOfGoodOperationsTipText() {
        return "Sets the Number of Good Operations per Look Ahead Step. 'nrOfGoodOperations = 5' means that for the next " + "Look Ahead Step only the 5 best Operations (adding, deleting or reversing an arc) are taken into account for the " + "calculation of the best sequence consisting of nrOfLookAheadSteps operations.";
    } // nrOfGoodOperationsTipText

} // LAGDHillClimber
